#include <stdio.h>
#include <stdlib.h>

// 判断数组是否是小根堆按层存储的结构
int isMinHeap(int arr[], int size) {
    // 从最后一个非叶子节点开始，依次向前遍历检查
    for (int i = (size - 2) / 2; i >= 0; i--) {
        int leftChildIndex = 2 * i + 1;
        int rightChildIndex = 2 * i + 2;

        // 获取左子节点的值，若左子节点索引超出范围，赋一个较大值便于比较
        int leftChild = (leftChildIndex < size)? arr[leftChildIndex] : __INT_MAX__;

        // 获取右子节点的值，若右子节点索引超出范围，赋一个较大值便于比较
        int rightChild = (rightChildIndex < size)? arr[rightChildIndex] : __INT_MAX__;

        // 如果当前节点大于它的左子节点或者右子节点，就不符合小根堆的性质
        if (arr[i] > leftChild || arr[i] > rightChild) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int arr1[] = {1, 3, 5, 7, 9, 11, 13};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int result1 = isMinHeap(arr1, size1);
    if (result1) {
        printf("数组 arr1 是小根堆按层存储的结构\n");
    } else {
        printf("数组 arr1 不是小根堆按层存储的结构\n");
    }

    int arr2[] = {1, 3, 2, 7, 9, 11, 13};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int result2 = isMinHeap(arr2, size2);
    if (result2) {
        printf("数组 arr2 是小根堆按层存储的结构\n");
    } else {
        printf("数组 arr2 不是小根堆按层存储的结构\n");
    }

    return 0;
}